package com.ruoyi.tcsp.test;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class BinaryTreeReconstruction {
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length != inorder.length) {
            return null;
        }
        Map<Integer, Integer> inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return buildTreeHelper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inorderMap);
    }

    private static TreeNode buildTreeHelper(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inorderMap) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);
        int rootInorderIndex = inorderMap.get(rootVal);
        int leftTreeSize = rootInorderIndex - inStart;

        root.left = buildTreeHelper(preorder, preStart + 1, preStart + leftTreeSize, inorder, inStart, rootInorderIndex - 1, inorderMap);
        root.right = buildTreeHelper(preorder, preStart + leftTreeSize + 1, preEnd, inorder, rootInorderIndex + 1, inEnd, inorderMap);

        return root;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();

        String[] parts = input.split("\\],\\[");
        if (parts.length != 2) {
            System.out.println("输入格式不正确，请重新输入。");
            return;
        }

        String preorderInput = parts[0].substring(1); // 去掉开头的 [
        String inorderInput = parts[1].substring(0, parts[1].length() - 1); // 去掉结尾的 ]

        int[] preorder = parseArray(preorderInput);
        int[] inorder = parseArray(inorderInput);

        TreeNode root = buildTree(preorder, inorder);

        // 可以在这里添加代码来验证重构的二叉树
        System.out.println("二叉树已成功重构。");
    }

    private static int[] parseArray(String input) {
        String[] parts = input.split(",");
        int[] array = new int[parts.length];
        for (int i = 0; i < parts.length; i++) {
            array[i] = Integer.parseInt(parts[i].trim());
        }
        return array;
    }
}
